//package com.qrpcw.algorithms;
//import java.util.ArrayList;
//import java.util.Arrays;
//
//
//public class PriorityQueue {
//
//	/**
//	 * @param args
//	 */
//	public static void main(String[] args) {
//		PriorityQueue queue = new PriorityQueue();
//		ArrayList<Integer>[] a = 
//			new ArrayList<Integer>[]{16,14,10,8,7,9,3,2,4,1}; 
//		queue.buildMaxHeap(a);
//		queue.heapMaximum(a);
//		queue.heapExtractMax(a);
//		System.out.println(Arrays.toString(a));
////		queue.heapIncreaseKey(a,0,17);
////		System.out.println(Arrays.toString(a));
//		queue.maxHeapInsert(a, 20);
//		System.out.println(Arrays.toString(a));
//	}
//	
//	private int parent(int i){ return (i-1)/2; }
//	private int left(int i){ return 2*i+1; } //leftChild position
//	private int right(int i){ return 2*i+2; } //rightChild position
//	private int heapMaximum(int[] A){ return A[0];};
//	
//	public void exchange(int[] A, int i,int j){
//		int temp;
//		temp = A[i]; 
//		A[i] = A[j]; 
//		A[j] = temp;
//	}
//	
//	public void maxHeapify(int[] A, int i, int heapSize){
//		int l = left(i);  //l=leftChild   i=root
//		int r = right(i); //r=rightChild
//		int largest;
//		if( l < heapSize && A[l] > A[i] ){
//			largest = l;
//		}else{
//			largest = i;
//		}
//		if( r < heapSize && A[r] > A[largest] ){
//			largest = r;
//		}
//		if(largest != i){
//			exchange(A,i,largest); //exchange child with root
//			maxHeapify(A,largest,heapSize);
//		}
//	}
//	
//	public void buildMaxHeap(int[] A){
//		int heapSize = A.length;
//		for(int i = (A.length/2)-1; i>=0; i--){
//			maxHeapify(A,i,heapSize);
//		}
//	}
//		
//	public int heapExtractMax(int[] A){
//		int heapSize = A.length;
//		if(heapSize <1){
//			System.out.println("heap underflow");
//		}
//		int max = A[0];
//		A[0] = A[heapSize-1];
//		heapSize = heapSize -1;
//		maxHeapify(A,0,heapSize);
//		return max;
//	}
//	
//	public void heapIncreaseKey(int[] A,int i,int key){
//		if(key < A[i]){
//			System.out.println("new key is smaller than current key");
//		}else{
//			A[i] = key;
//			while(i>=0 && A[parent(i)]<A[i]){
//				exchange(A, i, parent(i));
//				i = parent(i);
//			}
//		}
//	}
//	
//	public void maxHeapInsert(int[] A, int key){
//		int heapSize = A.length;
//		heapSize = heapSize + 1;
//		A[heapSize-1] = -10000;
//		heapIncreaseKey(A,heapSize-1,key);
//	}
//}
